//交换排序-》冒泡排序(升序)
//稳定（无间隔）
//时间复杂度：O(N^2)
//空间复杂度：O(1)
void BubbleSort(int* arr, int size) {
	for (int i = 0; i < size - 1; i++) {
		int flag = 0;
		for (int j = 0; j < size - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
		if (!flag)
			break;
	}
}

void SortPrint(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, size);
	SortPrint(arr, size);
	return 0;
}